#define MaxLen 65536
namespace History_{unsigned char Ret[2]{'\0','\0'};}
class History{
    unsigned char Stack1[MaxLen]{};
    unsigned char Stack2[MaxLen]{};
    unsigned int top1i=0,n1=0,curi=0;
    unsigned int top2i=0;

    public:
    void push(char rotLayer,char rotCount){
        bool curinq1=(top1i-curi)%MaxLen>=0&&(top1i-curi)%MaxLen<=n1;
        if(!curinq1)return;//curi不在Stack1有元素部分也不在栈顶
        unsigned char C=(rotCount-'0')%4;
        unsigned char L=0;
        switch (rotLayer){
            case 'U':L=0b001;break;
            case 'D':L=0b010;break;
            case 'R':L=0b011;break;
            case 'L':L=0b100;break;
            case 'F':L=0b101;break;
            case 'B':L=0b110;break;
            default:break;}
        //指令编码和压栈
        Stack1[top1i]=(L<<2)|C;
        //相关变量修改
        top2i=0;n1+=n1<(MaxLen-1);
        top1i++;top1i%=MaxLen;
    }
    void UndoRedo(char NextOrLast){
        switch (NextOrLast){
            case 'l':case 'L'://回溯
                if(   n1==0)return;//后退栈空
                top1i=(MaxLen+top1i-1)%MaxLen;n1--;
                Stack2[top2i]=Stack1[top1i];top2i++;
            break;// ↑两栈之间"倒手"操作
            case 'n':case 'N'://撤销回溯
                if(top2i==0)return;//前进栈空
                top2i--;Stack1[top1i]=Stack2[top2i];
                top1i++;top1i%=MaxLen;n1+=n1<(MaxLen-1);
            break;// ↑两栈之间"倒手"操作
            default:break;}
    }
    void getter(){
        //无代办
        if(isTaskAllClear()){History_::Ret[0]=0;History_::Ret[1]=0;return;}
        bool rev=false;//由于回溯得到的操作是原始操作的逆,记录是否需要求逆
        if((top1i-curi)%MaxLen>0&&(top1i-curi)%MaxLen<=n1){
            rev=false;History_::Ret[0]=Stack1[curi];
        }else{
            rev=true;History_::Ret[0]=Stack2[top2i-(MaxLen+curi-top1i)%MaxLen];
        }// ↓指令解码并放入暂存
        History_::Ret[1]=History_::Ret[0]&0b11;
        if(rev){History_::Ret[1]=4-History_::Ret[1];};
        History_::Ret[1]+='0';
        History_::Ret[0]>>=2;History_::Ret[0]&=0b1111;
        switch (History_::Ret[0]){
            case 0b001:History_::Ret[0]='U';break;
            case 0b010:History_::Ret[0]='D';break;
            case 0b011:History_::Ret[0]='R';break;
            case 0b100:History_::Ret[0]='L';break;
            case 0b101:History_::Ret[0]='F';break;
            case 0b110:History_::Ret[0]='B';break;
            default:break;}
        return ;
    }
    void next(){
        if(top1i==curi)return;
        if((top1i-curi)%MaxLen>0&&(top1i-curi)%MaxLen<=n1){
            curi+=MaxLen;curi++;curi%=MaxLen;
        }else{// ↑逻辑"内"情况,循环"步进"
            curi+=MaxLen;curi--;curi%=MaxLen;
        }//      ↑逻辑"外"情况,循环"步退"
    }
    bool isTaskAllClear(){
        return curi==top1i;
    }// curi正处栈顶代表无代办
};